Double hashing

 ( Search Algorithms ) 

Double hashing is a computer programming technique used in conjunction with open addressing in to resolve , by using a secondary hash of the key as an offset when a collision occurs. Double hashing with open addressing is a classical data structure on a table $T$.

The double hashing technique uses one hash value as an index into the table and then repeatedly steps forward an interval until the desired value is located, an empty location is reached, or the entire table has been searched; but this interval is set by a second, independent hash function. Unlike the alternative collision-resolution methods of linear probing and quadratic probing, the interval depends on the data, so that values mapping to the same location have different bucket sequences; this minimizes repeated collisions and the effects of clustering.

Given two random, uniform, and independent hash functions $h\_1$ and $h\_2$, the $i$th location in the bucket sequence for value $k$ in a hash table of $|T|$ buckets is: $h(i,k)=(h\_1(k)\; +\; i\; \backslash cdot\; h\_2(k))\backslash bmod|T|.$ Generally, $h\_1$ and $h\_2$ are selected from a set of universal hash functions; $h\_1$ is selected to have a range of $\backslash \{0,|T|-1\backslash \}$ and $h\_2$ to have a range of $\backslash \{1,|T|-1\backslash \}$. Double hashing approximates a random distribution; more precisely, pair-wise independent hash functions yield a probability of $(n/|T|)^2$ that any pair of keys will follow the same bucket sequence.

• It should never yield an index of zero.
• It should cycle through the whole table.
• It should be very fast to compute.
• It should be pair-wise independent of $h\_1(k)$.
• The distribution characteristics of $h\_2$ are irrelevant. It is analogous to a random-number generator.
• All $h\_2(k)$ should be relatively prime to | T|.

In practice:

• If division hashing is used for both functions, the divisors are chosen as primes.
• If | T| is a power of 2, the first and last requirements are usually satisfied by making $h\_2(k)$ always return an odd number. This has the side effect of doubling the chance of collision due to one wasted bit.

$$h(i,k)\; =\; (\; h\_1(k)\; +\; i\; \backslash cdot\; h\_2(k)\; )\; \backslash bmod\; |T|.$$

Let $T$ have fixed load factor $\backslash alpha:\; 1\; >\; \backslash alpha\; >\; 0$. Bradford and Katehakis. showed the expected number of probes for an unsuccessful search in $T$, still using these initially chosen hash functions, is $\backslash tfrac\{1\}\{1-\backslash alpha\}$ regardless of the distribution of the inputs. Pair-wise independence of the hash functions suffices.

Like all other forms of open addressing, double hashing becomes linear as the hash table approaches maximum capacity. The usual heuristic is to limit the table loading to 75% of capacity. Eventually, rehashing to a larger size will be necessary, as with all other open addressing schemes.

There are additionally a significant number of mostly-overlapping hash sets; if $h\_2(y)\; =\; h\_2(x)$ and $h\_1(y)\; =\; h\_1(x)\; \backslash pm\; h\_2(x)$, then $h(i,\; y)\; =\; h(i\backslash pm\; 1,\; x)$, and comparing additional hash values (expanding the range of $i$) is of no help.

         &= h_1(y) + (k - i) (-h_2(x) - 2k h_3(x)) + (k-i)^2 h_3(x) \\
         &= \ldots \\
         &= h_1(x) + k h_2(x) + k^2 h_3(x) + (i - k) h_2(x) + (i^2 - k^2) h_3(x) \\
         &= h_1(x) + i h_2(x) + i^2 h_3(x) \\
         &= h(i, x). \\
     

unsigned int a = h1(x), b = h2(x), i = 0;
     

   hashes[i] = a;
for (i = 1; i < n; i++) {
	a += b;	// Add quadratic difference to get cubic
	b += i;	// Add linear difference to get quadratic
	       	// i++ adds constant difference to get linear
	hashes[i] = a;
}